#include <iostream>
#include <vector>
using namespace std;

int mode = 0;       // 众数
int duplicates = 0; // 重数

// 返回中位数的重数和其首次出现位置
pair<int, int> Count(vector<int> vec, int low, int high)
{
    int count = 1;
    int mid = (low + high) >> 1;
    int i = 1;
    while (mid + i <= high && vec[mid + i] == vec[mid])
        count++, i++;

    i = 1;
    while (mid - i >= 0 && vec[mid - i] == vec[mid])
        count++, i++;
    return pair<int, int>(count, mid - i + 1);
}

void find_mode(vector<int> vec, int low, int high)
{
    if (low >= high)
        return;

    int mid = (low + high) >> 1;
    pair<int, int> mid_info = Count(vec, low, high);
    int mid_count = mid_info.first;  // 中位数出现次数
    int mid_first = mid_info.second; // 中位数首次出现位置

    // 存在重数相同的众数时，取小的
    if (mid_count >= duplicates)
    {
        mode = vec[mid];
        duplicates = mid_count;
    }

    // 如果右边剩余数多于当前众数
    if (high + 1 - (mid_first + mid_count) > duplicates)
        find_mode(vec, mid_first + mid_count, high);

    // 如果左边剩余数多于当前众数，则在左边继续找
    if (mid_first + 1 > duplicates)
        find_mode(vec, low, mid_first);
}

int main()
{
    mode = duplicates = 0;
    vector<int> nums{1, 1, 1, 2, 3, 3, 3};
    find_mode(nums, 0, nums.size() - 1);
    cout << "mode:" << mode << endl;
    cout << "duplicates:" << duplicates << endl;

    return 0;
}